home *** CD-ROM | disk | FTP | other *** search
/ BBS in a Box 4 / BBS in a Box - Macintosh - Volume IV (January 1992) (BBS in a Box).iso / Files / Prog / U-Z / Vax Storage < prev    next >
Encoding:
Text File  |  1987-11-28  |  3.5 KB  |  98 lines  |  [TEXT/MACA]
  1. { 
  2. This Pascal fragment illustrates how to calculate an XMODEM/YMODEM 
  3. type Cyclic Redundancy Check (CRC) with minimal performance overhead, 
  4. namely on a one-operation-per-byte basis.  It is nearly as fast as 
  5. the old arithmetic checksum.  Communications programmers who don't 
  6. know the "256 word table" trick will want to download this file so
  7. they can improve their code's performance.  Also curiosity-seekers 
  8. and for general education.
  9.  
  10. A SHORT HISTORY
  11.  
  12. The contributor has recently (11/25/87) written an XMODEM/YMODEM 
  13. program in VAX Pascal.  I planned to use the VAX CRC instruction
  14. but discovered it computed CRC's with the least-significant-bit of 
  15. each byte going in first, while the XMODEM/YMODEM CRC wants the 
  16. most-significant bit to be inserted first.  The table-driven 
  17. nature of the VAX instruction, and dissatisfaction with the overhead 
  18. of bitwise computation, led me to discover the algorithm shown here.
  19.  
  20. This has been tested by using an incorrect polynomial, which of course 
  21. leads to a hard error.  It has NOT been tested by injection of line 
  22. errors (direct link used on the system on which it was developed, and 
  23. no electriv drill handy).  It is free and public domain.  
  24.  
  25. { some type declarations to keep VAX Pascal happy.}
  26.  
  27. TYPE $UBYTE = [BYTE]0..255;  $UWORD = [WORD]0..65535;
  28.  
  29. {the following type aCRC is dependent on VAX storage allocation, 
  30.  and will be different on othe machines, particularly 16-bit ones.}
  31.  
  32.   aCRC = PACKED RECORD CASE INTEGER OF
  33.     1: (crc32 : UNSIGNED);
  34.     2: (crc16,hi16 : $UWORD);
  35.     3: (lsbyte,nlsbyte,nmsbyte,msbyte : $UBYTE);
  36.   END;
  37.  
  38. VAR crcTab : ARRAY [0..255] OF $UWORD; {global var, 16-bit entries}
  39.  
  40.  
  41. FUNCTION CRC(Buffer:PACKED ARRAY [1..1026] OF CHAR; Cnt:INTEGER):$UWORD;
  42.  
  43. {this function computes and returns the 16-bit CRC of the first (Cnt)
  44.   bytes in Buffer.  For XMODEM/YMODEM transmission, it would be called 
  45.   with Cnt=128 or 1024.  For reception, it would be called with Cnt=
  46.   130 or 1026.  (Including the CRC itself in the calculation should 
  47.   "cancel" the accumulation up to that point, and the returned value 
  48.   is 0 if all is well.)  The SOH/STX and the two record number bytes 
  49.   are not included in the CRC, and it's assumed they went somewhere 
  50.   else than in Buffer.
  51.   
  52.   UXOR is a VAX Pascal function that does a 32-bit Exclusive OR 
  53.       and returns an "unsigned" value.
  54.   UINT is a VAX Pascal type transfer function that returns "UNSIGNED".
  55.   ORD is a Pascal type transfer function that returns "INTEGER"
  56.   
  57.   In other words, UINT and ORD don't do anything useful...
  58.   }
  59. VAR i:INTEGER; compCRC:aCRC; 
  60. BEGIN
  61.     WITH compCRC DO BEGIN
  62.  
  63.     crc32:=0;
  64.     
  65.     FOR i:=1 to Cnt DO crc32:=
  66.     UXOR( lsbyte*256, crcTab[ ORD( UXOR( nlsbyte, UINT( Buffer[i])))]);
  67.  
  68.     CRC:=crc16;
  69.     END {WITH};
  70. END;
  71.  
  72. {in plainer terms: for each byte in Buffer, we compute a new 16-bit 
  73. CRC as
  74.  
  75. new CRC:=(oldCRC lo byte shifted left 8 bits, with 0's coming in)
  76.       XOR
  77.      crcTab[ (old CRC hi byte) XOR (the byte from Buffer) ]
  78.      
  79. where the contents of crcTab are computed at program startup by the 
  80. following subroutine:
  81. }
  82.  
  83.  
  84. PROCEDURE initCRCTab;
  85. VAR theCRC: aCRC; i,j:INTEGER;
  86. BEGIN
  87.     WITH theCRC DO 
  88.     FOR i:=0 TO 255 DO BEGIN        {fill up the table}
  89.     crc32:=i*256;             {index value shifted 8 right}
  90.     FOR j:=1 to 8 DO BEGIN      {test each of the 8 hi bits}
  91.         crc32:=crc32+crc32;     {left shift all 16 by 1}
  92.         IF hi16>0 THEN         {and if the bit shifted out is 1}
  93.         crc32:= UXOR(crc16,%X'1021'); {then XOR in the polynomial}
  94.     END {FOR j};            {for all 8}
  95.     crcTab[i]:=crc16;        {put the result in the table}
  96.     END {FOR i};
  97. END;